package com.zlk.algorithm.algorithm.dynamicPlan.twoDimension;

// 矩阵中的最长递增路径
// 给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度
// 对于每个单元格，你可以往上，下，左，右四个方向移动
// 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）
// 测试链接 : https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/
public class Code06_LongestIncreasingPath {

    public int longestIncreasingPath(int[][] matrix) {


        int row = matrix.length;
        int col = matrix[0].length;

        int[][] dp = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                dp[i][j] = -1;
            }
        }

        int ans = 1;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                //ans = Math.max(f1(matrix,i,j),ans);
                ans = Math.max(f2(matrix,i,j,dp),ans);
            }
        }
        return ans;

    }

    public static int f11(int[][] grid, int i, int j) {
        int next = 0;
        if (i > 0 && grid[i][j] < grid[i - 1][j]) {
            next = Math.max(next, f11(grid, i - 1, j));
        }
        if (i + 1 < grid.length && grid[i][j] < grid[i + 1][j]) {
            next = Math.max(next, f11(grid, i + 1, j));
        }
        if (j > 0 && grid[i][j] < grid[i][j - 1]) {
            next = Math.max(next, f11(grid, i, j - 1));
        }
        if (j + 1 < grid[0].length && grid[i][j] < grid[i][j + 1]) {
            next = Math.max(next, f11(grid, i, j + 1));
        }
        return next + 1;
    }



    private int f2(int[][] matrix, int i, int j, int[][] dp) {
        if(dp[i][j]!=-1){
            return dp[i][j];
        }
        int row = matrix.length;
        int col = matrix[0].length;
        int ans =0;
        if(i-1>=0&&matrix[i-1][j]>matrix[i][j]){
            ans = Math.max(ans,1+f2(matrix,i-1,j,dp));
        }

        if(j-1>=0&&matrix[i][j-1]>matrix[i][j]){
            ans = Math.max(ans,1+f2(matrix,i,j-1,dp));
        }

        if(i+1<row&&matrix[i+1][j]>matrix[i][j]){
            ans = Math.max(ans,1+f2(matrix,i+1,j,dp));
        }

        if(j+1<col&&matrix[i][j+1]>matrix[i][j]){
            ans = Math.max(ans,1+f2(matrix,i,j+1,dp));
        }
        if(ans==0){
            dp[i][j]=1;
            return 1;
        }else{
            dp[i][j]=ans;
            return ans;
        }
    }

    /**
     * 递归含义  从i j位置出发，最大递增长度
     * @param matrix
     * @param i
     * @param j
     * @return
     */
    private int f1(int[][] matrix, int i, int j) {
        int row = matrix.length;
        int col = matrix[0].length;
        int ans =0;
        if(i-1>=0&&matrix[i-1][j]>matrix[i][j]){
            ans = Math.max(ans,1+f1(matrix,i-1,j));
        }

        if(j-1>=0&&matrix[i][j-1]>matrix[i][j]){
            ans = Math.max(ans,1+f1(matrix,i,j-1));
        }

        if(i+1<row&&matrix[i+1][j]>matrix[i][j]){
            ans = Math.max(ans,1+f1(matrix,i+1,j));
        }

        if(j+1<col&&matrix[i][j+1]>matrix[i][j]){
            ans = Math.max(ans,1+f1(matrix,i,j+1));
        }
        if(ans==0){
            return 1;
        }else{
            return ans;
        }
    }
}
